﻿// kv_skiplist.h: 标准系统包含文件的包含文件
// 或项目特定的包含文件。

#pragma once


/**
 *                    _ooOoo_
 *                   o8888888o
 *                   88" . "88
 *                   (| -_- |)
 *                    O\ = /O
 *                ____/`---'\____
 *              .   ' \\| |// `.
 *               / \\||| : |||// \
 *             / _||||| -:- |||||- \
 *               | | \\\ - /// | |
 *             | \_| ''\---/'' | |
 *              \ .-\__ `-` ___/-. /
 *           ___`. .' /--.--\ `. . __
 *        ."" '< `.___\_<|>_/___.' >'"".
 *       | | : `- \`.;`\ _ /`;.`/ - ` : | |
 *         \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 *                    `=---='
 *
 * .............................................
 *          佛祖保佑             永无BUG
 */

 /**
  *  佛曰:
  *          写字楼里写字间，写字间里程序员；
  *          程序人员写程序，又拿程序换酒钱。
  *          酒醒只在网上坐，酒醉还来网下眠；
  *          酒醉酒醒日复日，网上网下年复年。
  *          但愿老死电脑间，不愿鞠躬老板前；
  *          奔驰宝马贵者趣，公交自行程序员。
  *          别人笑我忒疯癫，我笑自己命太贱；
  *          不见满街漂亮妹，哪个归得程序员？
  */


#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <mutex>
#include <fstream>
#include <string>

// 文件保存位置
#define STORE_FILE "store/dumpFile"

std::mutex mtx;
std::string delimiter = ":";

template<typename K,typename V>
class Node {
public:
	Node() {};
	Node(K k, V v, int);
	
	~Node(); 

	K get_key() const;

	V get_value() const;

	void set_value(V);

	// 指针数组  由指针构成的数组
	/*
	*  a.forward[0]        = new Node<int,std::string>;
	   a.forward[0]->key   = 10;
	   a.forward[0]->value = "1232";
	*/
	Node<K, V>** forward;

	int node_level;

private:
	K key;
	V value;

};

template<typename K, typename V>
Node<K, V>::Node(const K k, const V v, int level) {
	this->key = k;
	this->value = v;
	this->node_level = level;

	this->forward = new Node<K, V>* [level + 1];
	memset(this->forward, 0, sizeof(Node<K, V>*) * (level + 1));

}

template<typename K, typename V>
Node<K, V>::~Node() {
	delete[]forward;
}

template<typename K, typename V>
K Node<K, V>::get_key() const {
	return key;
}

template<typename K, typename V>
V Node<K, V>::get_value() const {
	return value;
}
template<typename K, typename V>
void Node<K, V>::set_value(V value) {
	this->value = value;
}



template<typename K,typename V>
class SkipList {
public:
	SkipList(int);
	~SkipList(); 
	int get_random_level();
	Node<K, V>* create_node(K, V, int);
	int insert_element(K, V);
	void display_list();
	bool search_element(K);
	void delete_element(K);
	void dump_file();
	void load_file();

	// 递归删除节点
	void clear(Node<K, V>*);
	int size();

private:
	void get_key_value_from_string(const std::string& str, std::string* key, std::string* value);
	bool is_valid_string(const std::string& str);

private:
	int _max_level;

	//   跳表的层数  0层为最全面的  
	int _skip_list_level;

	// header指向的forward[i] 这个node  储存的 是 第i层的第一个node   第i层的第一个node 的forward[i] 就是第i层的第一个node 的下一个node
	Node<K, V>* _header;
	std::ofstream _file_writer;
	std::ifstream _file_reader;

	int _element_count;
};


// 构造函数
template<typename K, typename V>
SkipList<K, V>::SkipList(int max_level)
{
	this->_max_level = max_level;
	this->_skip_list_level = 0;
	this->_element_count = 0;

	K k;
	V v;
	this->_header = new Node<K, V>(k, v, _max_level);
}


// 析构函数
template<typename K, typename V>
SkipList<K, V>::~SkipList()
{
	if (_file_writer.is_open())
		_file_writer.close();

	if (_file_reader.is_open()) 
		_file_reader.close();

	//递归删除跳表链条

	if (_header->forward[0] != nullptr) {
		clear(_header->forward[0]);
	}
	delete(_header);

}


// 清除节点
template <typename K, typename V>
void SkipList<K, V>::clear(Node<K, V>* cur)
{
	if (cur->forward[0] != nullptr)
		clear(cur->forward[0]);
	delete(cur);
}


// 创建节点
template<typename K, typename V>
Node<K, V>* SkipList<K, V>::create_node(const K k, const V v, int level)
{
	Node<K, V>* n = new Node<K, V>(k, v, level);
	return n;
}

// 获取数量
template<typename K, typename V>
int SkipList<K, V>::size()
{
	return _element_count;
}

// 获取随机数 通过随机数来获取层数  取 当前层数和连续随机数个数的较小值  返回
template<typename K, typename V>
int SkipList<K, V>::get_random_level()
{
	int k = 1;
	while (rand() % 2) {
		k++;
	}
	k = (k < _max_level) ? k : _max_level;
	return k;

}



// 打印 所有的元素
template<typename K, typename V>
void SkipList<K, V>::display_list()
{
	std::cout << "\n*****Skip List*****" << "\n";
	for (int i = 0; i <= _skip_list_level; i++)
	{
		Node<K, V>* node = this->_header->forward[i];
		std::cout << " Level " << i << " : ";
		while (node != NULL)
		{
			std::cout << node->get_key() << " : " << node->get_value() << " ; ";
			node = node->forward[i];
		}
		std::cout << std::endl;
	}
}

// 判断是不是合法字符  返回真 为 合法  返回假  不合法 
template<typename K, typename V>
bool SkipList<K, V>::is_valid_string(const std::string& str)
{
	// 空字符串
	if (str.empty())
		return false;

	// 表示这个字符串并不存在 delimiter 也就是 :
	if (str.find(delimiter) == std::string::npos)
		return false;

	return true;
}


// 将一个类似    12:语文   的字符串 转化为  key: 12   value : 语文   的k-v类型
// delimiter 表示的是 ： 
template<typename K, typename V>
void SkipList<K, V>::get_key_value_from_string(const std::string& str, std::string* key, std::string* value)
{
	// 不合法
	if (!is_valid_string(str))
	{
		return;
	}

	*key = str.substr(0, str.find(delimiter));
	*value = str.substr(str.find(delimiter) + 1, str.length());
}


// 保存数据到文件中 STORE_FILE "store/dumpFile"
template<typename K, typename V>
void SkipList<K, V>::dump_file()
{
	std::cout << "dump_file-----------------" << std::endl;
	_file_writer.open(STORE_FILE);
	Node<K, V>* node = this->_header->forward[0];

	while (node != nullptr)
	{
		_file_writer << node->get_key() << ":" << node->get_value() << "\n";
		std::cout<< node->get_key() << ":" << node->get_value() << ";\n";
		node = node->forward[0];
	}

	_file_writer.flush();
	_file_writer.close();
	return;

}


// 查询这个值 存在返回T  不存在返回F  使用跳表数据类型特性实现
template<typename K, typename V>
bool SkipList<K, V>::search_element(K key)
{
	std::cout << "search_element-----------------" << std::endl;
	Node<K, V>* current = _header;

	// 从最上层开始 
	for (int i = _skip_list_level; i >= 0; i--)
	{
		// 在当前层一直向右走 直到遇到大于key的值就 跳到更细微的下一层寻找
		while (current->forward[i] && current->forward[i]->get_key() < key)
		{
			current = current->forward[i];
		}
	}

	// 寻找到了第0层 ， 那么currennt->forward[0] 一定是大于等于key或者为null的
	current = current->forward[0];

	if (current && current->get_key() == key)
	{
		std::cout << "Found key: " << key << ", value: " << current->get_value() << std::endl;
		return true;
	}

	std::cout << "Not Found Key:" << key << std::endl;
	return false;
}


template<typename K, typename V>
int SkipList<K, V>::insert_element(const K key, const V value)
{
	mtx.lock();
	// 跳表的头一个 指针
	Node<K, V>* current = this->_header;

	// 最大限度的Node 指针的数组  这个数组用于储存每一层中 小于key的最大的node的指针
	Node<K, V>* update[_max_level + 1];
	// Node <K, V>** update = new Node<K, V>* [_max_level + 1];
	memset(update, 0, sizeof(Node<K, V>*) * (_max_level + 1));

	for (int i = _skip_list_level; i >= 0; i--)
	{
		while (current->forward[i] != NULL && current->forward[i]->get_key() < key)
		{
			current = current->forward[i];
		}
		update[i] = current;
	}


	// 寻找到了第0层 ， 那么currennt->forward[0] 一定是大于等于key或者为null的
	current = current->forward[0];

	// 如果跳表中已经存在了这个值  那么不做修改直接返回
	if (current != NULL && current->get_key() == key) 
	{
		std::cout << "key: " << key << ", exists" << std::endl;
		mtx.unlock();
		return 1;
	}

	// 跳表中不存在这个值  
	if (current == NULL || current->get_key() != key)
	{
		// 取一个随机层数  该随机层数小于最大层数
		int random_level = get_random_level();
		// 随机层数大于当前层数
		if (random_level > _skip_list_level)
		{
			for (int i = _skip_list_level+1; i < random_level+1; i++)
			{
				// 对于新增加的层数中 header->forward[new level] 需要进行一个指向 ， 所以将新的 newlevel 也储存在update之中
				update[i] = _header;
			}
			// 更新 当前层数
			_skip_list_level = random_level;
		}

		// 创建节点
		Node<K, V>* inserted_node = create_node(key, value, random_level);

		for (int i = 0; i <= random_level; i++)
		{
			//  这个过程相当于  new1  想要插入  t1（小于new1) -> t2(大于new1) 之中
			// 于是 new1->t2   t1->new1  最终 t1->new1->t2
			// 对每一层都进行这样
			inserted_node->forward[i] = update[i]->forward[i];
			update[i]->forward[i] = inserted_node;
		}
		std::cout << "Successfully inserted key:" << key << ", value:" << value << std::endl;
		_element_count++;

	}

	mtx.unlock();
	return 0;
}




template<typename K, typename V>
void SkipList<K, V>::load_file()
{
	_file_reader.open(STORE_FILE);
	std::cout << "load_file-----------------" << std::endl;
	std::string line;
	std::string* key = new std::string();
	std::string* value = new std::string();
	while (getline(_file_reader, line)) {
		get_key_value_from_string(line, key, value);
		if (key->empty() || value->empty()) {
			continue;
		}
		// Define key as int type
		insert_element(stoi(*key), *value);
		std::cout << "key:" << *key << "value:" << *value << std::endl;
	}
	delete key;
	delete value;
	_file_reader.close();
}





template<typename K, typename V>
void SkipList<K, V>::delete_element(K key)
{
	mtx.lock();
	Node<K, V>* current = this->_header;
	Node<K, V>* update[_max_level + 1];
	memset(update, 0, sizeof(Node<K, V>*) * (_max_level + 1));

	for (int i = _skip_list_level; i >= 0; i--) {
		while (current->forward[i] != NULL && current->forward[i]->get_key() < key) {
			current = current->forward[i];
		}
		// 在每一层中寻找 小于这个节点的 最大的值
		update[i] = current;
	}

	current = current->forward[0];

	if (current != NULL && current->get_key() == key)
	{
		for (int i = 0; i <= _skip_list_level; i++)
		{
			// 如果这一层不存在 这个值那么退出所有循环
			if (update[i]->forward[i] != current)
				break;

			// 这一层存在这个值 就将节点后移  如   t1 -> target -> t2  ----->   t1->t2
			update[i]->forward[i] = current->forward[i];
		}

		// 如果最上层 仅有这一个删除的值 那么层数就减一
		while (_skip_list_level > 0 && _header->forward[_skip_list_level] == 0) {
			_skip_list_level--;
		}

		std::cout << "Successfully deleted key " << key << std::endl;
		delete current;
		_element_count--;


	}


	mtx.unlock();
	return;

}


